/*
 * @lc app=leetcode.cn id=28 lang=cpp
 * @lcpr version=30204
 *
 * [28] 找出字符串中第一个匹配项的下标
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution
{
public:
    vector<int> getNext(const string &pattern)
    {
        int m = pattern.size();
        vector<int> next(m, 0);
        int len = 0; // 当前最长公共前后缀长度

        for (int i = 1; i < m;)
        {
            if (pattern[i] == pattern[len])
            {
                next[i++] = ++len;
            }
            else
            {
                if (len != 0)
                    len = next[len - 1]; // 回到字串公共前后缀的地方
                else
                    next[i++] = 0;
            }
        }

        return next;
    }

    int strStr(string haystack, string needle)
    {
        vector<int> next = getNext(needle);
        int m = haystack.size();
        int n = needle.size();
        int i = 0, j = 0;
        while (i < m)
        {
            if (haystack[i] == needle[j])
            {
                i++;
                j++;
                if (j == n)
                {
                    return i - j;
                }
            }
            else
            {
                if (j != 0)
                {
                    j = next[j - 1];
                }
                else
                    ++i;
            }
        }
        return -1;
    }
};
// @lc code=end

/*
// @lcpr case=start
// "sadbutsad"\n"sad"\n
// @lcpr case=end

// @lcpr case=start
// "leetcode"\n"leeto"\n
// @lcpr case=end

 */
